#include "DoubleLinkList.h"

DoubleLinkList::DoubleLinkList() : size(0)
{
    head = tail = new Node(0);
    Free = nullptr;
}

DoubleLinkList::~DoubleLinkList()
{
    Node *travelPoint = head->next;
    while (travelPoint != nullptr)
    {
        if (Free);
        Free(travelPoint->value);
        Node *freeNode = travelPoint;
        travelPoint = travelPoint->next;
        delete freeNode;
    }
    delete head;
    tail = nullptr;
}

DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    this->size = list.size;

    head = tail = new Node(0);

    Node *travelaPoint = list.head->next;
    while (travelaPoint != nullptr)
    {
        // 构建一个新的节点用于存储每一个待拷贝的节点值

        Node *newNode = new Node(travelaPoint->value);
        Copy = list.Copy;
        Free = list.Free;
        Print = list.Print;
        newNode->value = Copy(travelaPoint->value);
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
        travelaPoint = travelaPoint->next;
    }
}

DoubleLinkList DoubleLinkList::operator=(const DoubleLinkList &list)
{
    Node *travelPoint = head->next;
    while (travelPoint != nullptr)
    {
        Free(travelPoint->value);
        Node *freeNode = travelPoint;
        travelPoint = travelPoint->next;
        delete freeNode;
    }
    delete head;
    tail = nullptr;
    this->size = list.size;
    head = tail = new Node(0);

    Node *travelaPoint = list.head->next;

    while (travelaPoint != nullptr)
    {
        // 构建一个新的节点用于存储每一个待拷贝的节点值
        Node *newNode = new Node(travelaPoint->value);
        // Copy = list.Copy;
        // Free = list.Free;
        // Print = list.Print;
        newNode->value = Copy(travelaPoint->value);
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
        travelaPoint = travelaPoint->next;
    }
    return *this;
}

// O(1)
void DoubleLinkList::InsertTail(const ElementType &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element)
{
    if (index > size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }

    Node *travelPoint = head;
    for (size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;
    travelPoint->next = newNode;
    if(size != 0)
    newNode->next->prev = newNode;
    size++;
}

void DoubleLinkList::RemoveByIndex(size_t index)
{
    if (index > size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }

    Node *travelPoint = head;
    for (size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }

    Node *freeNode = travelPoint->next;
    if (freeNode != tail)
    {
        travelPoint->next = freeNode->next;
        if(freeNode->next)
        freeNode->next->prev = travelPoint;
        if(Free)
        Free(freeNode->value);
        delete freeNode;
        size--;
    }
    else
    {
        travelPoint->next = freeNode->next;
        tail = travelPoint;
        if(Free)
        Free(freeNode->value);
        delete freeNode;
        size--;
    }
}

void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if (travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            if (freeNode != tail)
            {
                travelPoint->next = freeNode->next;
                freeNode->next->prev = travelPoint;
                delete freeNode;
                size--;
            }
            else
            {
                travelPoint->next = freeNode->next;
                tail = travelPoint;
                delete freeNode;
                size--;
            }
        }
        else
        {
            travelPoint = travelPoint->next;
        }
    }
}

DoubleLinkList::ElementType *DoubleLinkList::FindByIndex(size_t index)
{
    if (index > size)
    {
        std::cout << "位置非法" << std::endl;
        return nullptr;
    }

    Node *travelPoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return &travelPoint->value;
}

// DARRAY::DynamicArray DoubleLinkList::FindeByElement(const DoubleLinkList::ElementType &element)
// {
//     DARRAY::DynamicArray result;
//     Node *travelPoint = head->next;
//     while (travelPoint != nullptr)
//     {
//         if (Compare(travelPoint->value, element) == 0)
//         {
//             result.InsertTail(travelPoint->value);
//         }
//         travelPoint = travelPoint->next;
//     }
//     return result;
// }

void DoubleLinkList::UpdateByIndex(size_t index, const DoubleLinkList::ElementType &element)
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }
    Node *travelPoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
}

void DoubleLinkList::Sort()
{
    FastSort(head->next, nullptr);
}

void DoubleLinkList::show()
{
    std::cout << "size:" << size << std::endl;
    Node *travePoint = head->next;
    // 链表还没结束
    while (travePoint != nullptr)
    {
        Print(travePoint->value);
        // 遍历指针往后走
        travePoint = travePoint->next;
    }
    std::cout << std::endl;

    travePoint = tail;
    while (travePoint != head)
    {
        Print(travePoint->value);
        travePoint = travePoint->prev;
    }
    std::cout << std::endl;
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    // 终止条件
    if (start == end)
    {
        return;
    }
    // 基准值指针
    Node *temp = start;
    // 慢指针
    Node *slow = start;
    // 快指针
    Node *fast = start->next;
    // 快指针没有到结尾
    while (fast != end)
    {
        // 快指针指向的值比基准值小
        if (Compare(fast->value, temp->value) == -1)
        {
            slow = slow->next;
            // 交换快慢指针的值
            // 将比基准值小的都换到一边
            // slow记录小于基准值的值
            std::swap(slow->value, fast->value);
        }
        fast = fast->next;
    }
    // 将基准值归位
    std::swap(temp->value, slow->value);
    //[start,slow)左闭右开
    FastSort(start, slow);
    FastSort(slow->next, end);
}
